package 二分查找.easy;

import java.util.HashMap;

/**
 * 1. 问题描述
 *      稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
 *
 * 2. 算法分析
 *      1. hashmap
 *
 *      2. 由于是一个稀疏数组，数组中很多空字符串，如果线性查询可能很多时间都浪费在无效的查询上了
 *         对于稀疏数组的查询，如何才能做到高效呢?
 *
 *         思路1：将稀疏的数组转换为一个紧凑格式的数组，然后查询这个紧凑个数的数组(或者其他的数据结构)
 *               实际上第一种方式 创建hashmap就是类似的。但是时间复杂度和消耗都比较高
 *
 *         思路2：
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 稀疏数组搜索 {
    public static void main(String[] args) {
        String s = "abc";
        System.out.println(s == "abc");
    }

    /**
     * 算法实现1：采用hasmap key为字符串 value为该字符串在words中的索引
     * 主要的时间复杂度在建立hashmap上，效率低，而且空间复杂度也比较高
     * @param words
     * @param s
     * @return
     */
    public static int findString(String[] words, String s) {
        HashMap<String,Integer> map = new HashMap<>();
        for(int i = 0; i < words.length; i++) {
            if(words[i] != "") {
                map.put(words[i],i);
            }
        }
        return (map.containsKey(s)) ? map.get(s) : -1;
    }

    /**
     * 优化算法：典型的二分查找算法
     * @param words
     * @param s
     * @return
     */
    public static int findString2(String[] words, String s) {

        return 0;
    }
}

